# 黑白棋
class TreeNode
  attr_accessor :val, :children,:score,:max,:index

  # The Tree node contains a value, and a pointer to two children - left and right 
  # Values lesser than this node will be inserted on its left
  # Values greater than it will be inserted on its right
  def initialize val,children,max
      @val = val
      @children = children
      @score = -999
      @max = max
      @index = 0
  end

  def insert(val)
    @children.push(val)
  end
end



def  maxMinSearch(matrix,depth,max,head,size)
  nextstep = step(matrix,max,size)
  if nextstep.length == 0 || depth == 2
    return score(matrix,size)
  end
  current = 1
  if max == false
    current = -1
  end
  cDepth = depth + 1
  maxOrMin = max == false ? true:false
  p nextstep
  for k in 0..nextstep.length - 1
    dupMatrix = copy(matrix,size)
    #新的点
    i = nextstep[k][0]
    j = nextstep[k][1]
    reverse(dupMatrix,i,j,current,size)
    
    child = TreeNode.new(dupMatrix,[],maxOrMin)
    head.insert(child)
    score = maxMinSearch(dupMatrix,cDepth,maxOrMin,child,size)
    #puts("score=" + score.to_s + ",max=" + maxOrMin.to_s + ",depth = " + cDepth.to_s)
  end
end

def copy(oldMatrix,size)
  matrix = []
  for i in 0..size - 1
    array = []
    for j in 0..size - 1
      array[j] = oldMatrix[i][j]
    end
    matrix.push(array)
  end
  return matrix
end

# 得分计算
def score(matrix,size)
  score = 0
  for i in 0..size - 1
    for j in 0..size - 1
      score = score + matrix[i][j]  
    end
  end
  return score
end

#反转
def reverse(matrix,i,j,current,size)
  matrix[i][j] = current
  nextp = -1 * current
  reverse1(matrix,i,j,current,nextp,size)
  reverse2(matrix,i,j,current,nextp,size)
  reverse3(matrix,i,j,current,nextp,size)
  reverse4(matrix,i,j,current,nextp,size)
  reverse5(matrix,i,j,current,nextp,size)
  reverse6(matrix,i,j,current,nextp,size)
  reverse7(matrix,i,j,current,nextp,size)
  reverse8(matrix,i,j,current,nextp,size)
end



#纵向往下
def reverse1(matrix,i,j,current, nextp,size)
  if  i < size - 2
    k = i + 1
    while k <  size - 1
      if matrix[k][j] == nextp
        k = k + 1
      else
          break
      end
    end
    if k < size && k > i + 1 && matrix[k][j] == current
      for p in i+1..k-1
        matrix[p][j] = current
      end
    end
  end
end

# 纵向往上
def reverse2(matrix,i,j,current, nextp,size)
  if  i > 1
    k = i - 1
    while k > 0
      if matrix[k][j] == nextp
        k = k - 1
      else
          break
      end
    end
    if k >= 0 && k < i - 1 && matrix[k][j] == current
      for p in k+1..i-1
        matrix[p][j] = current
      end
    end
  end
end


# 横向往右
def reverse3(matrix,i,j,current, nextp,size)
  
  if  j < size - 2
    k = j + 1
    while k <  size - 1
      if matrix[i][k] == nextp
        k = k + 1
      else
          break
      end
    end
    if k < size && k > j + 1 && matrix[i][k] == current
      for p in j+1..k-1
        matrix[i][p] = current
      end
    end
  end
end

# 横向往左
def reverse4(matrix,i,j,current, nextp,size)
  if  j > 1
    k = j - 1
    while k > 0
      if matrix[i][k] == nextp
        k = k - 1
      else
          break
      end
    end
    if k >= 0 && k < j - 1 && matrix[i][k] == current
      for p in k+1..j-1
        matrix[i][p] = current
      end
    end
  end
end

# 右下
def reverse5(matrix,i,j,current, nextp,size)
  if  i < size - 2 && j < size - 2
    k = i + 1
    m = j + 1
    while k <  size - 1 && m < size - 1
      if matrix[k][m] == nextp
        k = k + 1
        m = m + 1
      else
          break
      end
    end
    if k < size && m < size && k > i + 1 && matrix[k,m] == current
      for p in i+1..k-1
        matrix[p][j+p-i] = current
      end
    end
  end
end

# 右上
def reverse6(matrix,i,j,current, nextp,size)
  if  i  > 1 && j < size - 2
    k = i - 1
    m = j + 1
    while k > 0 && m < size - 1
      if matrix[k][m] == nextp
        k = k - 1
        m = m + 1
      else
          break
      end
    end
    if k >= 0 && m < size  && k < i - 1 && m > j + 1 && matrix[k,m] == current
      for p in k+1..i-1
        matrix[p][j-p+k] = current
      end
    end
  end
end

# 左下
def reverse7(matrix,i,j,current, nextp,size)
  if  i < size - 2 && j > 1
    k = i + 1
    m = j - 1
    while k <  size - 1 && m > 0
      if matrix[k][m] == nextp
        k = k + 1
        m = m - 1
      else
          break
      end
    end
    if k < size && m >= 0 && k > i + 1 && m < j- 1 && matrix[k,m] == current
      for p in i+1..k-1
        matrix[p][j-p+i] = current
      end
    end
  end
end

# 左上
def reverse8(matrix,i,j,current, nextp,size)
  if  i > 1 && j > 1
    k = i - 1
    m = j - 1
    while k > 0 && m > 0
      if matrix[k][m] == nextp
        k = k - 1
        m = m - 1
      else
          break
      end
    end
    if k >= 0 && m >= 0 && k < i + 1 && m < j- 1 && matrix[k,m] == current
      for p in k+1..i-1
        matrix[p][j+p-k] = current
      end
    end
  end
end

# 纵向往下
def findStep1(matrix,i,j,current, nextp,newstep,size)
  if  i < size - 2
    k = i + 1
    while k <  size - 1
      if matrix[k][j] == nextp
        k = k + 1
      else
          break
      end
    end
    if k < size && k > i + 1 && matrix[k][j] == 0
      newstep.push([k,j])
    end
  end
end

# 纵向往上
def findStep2(matrix,i,j,current, nextp,newstep,size)
  if  i > 1
    k = i - 1
    while k > 0
      if matrix[k][j] == nextp
        k = k - 1
      else
          break
      end
    end
    if k >= 0 && k < i - 1 && matrix[k][j] == 0
      newstep.push([k,j])
    end
  end
end


# 横向往右
def findStep3(matrix,i,j,current, nextp,newstep,size)
  if  j < size - 2
    k = j + 1
    while k <  size - 1
      if matrix[i][k] == nextp
        k = k + 1
      else
          break
      end
    end
    if k < size && k > j + 1 && matrix[i][k] == 0
      newstep.push([i,k])
    end
  end
end


# 横向往左
def findStep4(matrix,i,j,current, nextp,newstep,size)
  if  j > 1
    k = j - 1
    while k > 0
      if matrix[i][k] == nextp
        k = k - 1
      else
          break
      end
    end
    if k >= 0 && k < j - 1 && matrix[i][k] == 0
      newstep.push([i,k])
    end
  end
end

# 右下
def findStep5(matrix,i,j,current, nextp,newstep,size)
  if  i < size - 2 && j < size - 2
    k = i + 1
    m = j + 1
    while k <  size - 1 && m < size - 1
      if matrix[k][m] == nextp
        k = k + 1
        m = m + 1
      else
          break
      end
    end
    if k < size && m < size && k > i + 1 && matrix[k,m] == 0
      newstep.push([k,m])
    end
  end
end

# 右上
def findStep6(matrix,i,j,current, nextp,newstep,size)
  if  i  > 1 && j < size - 2
    k = i - 1
    m = j + 1
    while k > 0 && m < size - 1
      if matrix[k][m] == nextp
        k = k - 1
        m = m + 1
      else
          break
      end
    end
    if k >= 0 && m < size  && k < i - 1 && m > j + 1 && matrix[k,m] == 0
      newstep.push([k,m])
    end
  end
end

# 左下
def findStep7(matrix,i,j,current, nextp,newstep,size)
  if  i < size - 2 && j > 1
    k = i + 1
    m = j - 1
    while k <  size - 1 && m > 0
      if matrix[k][m] == nextp
        k = k + 1
        m = m - 1
      else
          break
      end
    end
    if k < size && m >= 0 && k > i + 1 && m < j- 1 && matrix[k,m] == 0
      newstep.push([k,m])
    end
  end
end

# 左上
def findStep8(matrix,i,j,current, nextp,newstep,size)
  if  i > 1 && j > 1
    k = i - 1
    m = j - 1
    while k > 0 && m > 0
      if matrix[k][m] == nextp
        k = k - 1
        m = m - 1
      else
          break
      end
    end
    if k >= 0 && m >= 0 && k < i + 1 && m < j- 1 && matrix[k,m] == 0
      newstep.push([k,m])
    end
  end
end

def step(matrix,max,size)
  newstep = []
  current = 1
  nextp = -1
  if max == false
    current = -1
    nextp = 1
  end
  
  for i in 0..size-1
      for j in 0..size-1
        if matrix[i][j] == current
          findStep1(matrix,i,j,current,nextp,newstep,size)

          findStep2(matrix,i,j,current,nextp,newstep,size)

          findStep3(matrix,i,j,current,nextp,newstep,size)

          findStep4(matrix,i,j,current,nextp,newstep,size)

          findStep5(matrix,i,j,current,nextp,newstep,size)

          findStep6(matrix,i,j,current,nextp,newstep,size)

          findStep7(matrix,i,j,current,nextp,newstep,size)

          findStep8(matrix,i,j,current,nextp,newstep,size)
           
        end       
      end
  end
 return newstep
end



def findStep(matrix)
  size = 4
  root = TreeNode.new(matrix,[],true)
  maxMinSearch(matrix,0,true,root,size)
  # 计算得分
  if root.children.length > 0
    for i in 0..root.children.length - 1
      child1 = root.children[i]
      score = 999
      index = 0
      if child1.children.length > 0
        for j in 0..child1.children.length - 1
          child2 = child1.children[j]
            if child2 != nil
                child2.score = score(child2.val,size)
                p "i=" + i.to_s + ",j=" + j.to_s +  ",score=" + child2.score.to_s
                # 极小
                if child2.score < score
                  score = child2.score
                  index = j
                end
                # 剪枝
                if child2.score <= root.score
                  break
                end
            end
        end
        child1.score = score
        child1.index = index
        if child1.score > root.score
          root.score = child1.score
          root.index = i 
        end
      end
      p "i=" + i.to_s + ",score=" + child1.score.to_s
      
    end
    maxScore = -999
    maxIndex = 0
    for i in 0..root.children.length - 1
      child1 = root.children[i]
      if child1.score > maxScore
        maxScore = child1.score
        maxIndex = i
      end
    end
    root.score = maxScore
    root.index = maxIndex
    p root.score
    p root.index
    p root.children[root.index].val
  end
end

matrix1 = [[0,0,0,0],[0,1,-1,0],[0,-1,1,0],[0,0,0,0]]
findStep(matrix1)
puts "----------------------------------------------------"
matrix2 = [[0,0,0,0],[0,1,-1,0],[0,-1,1,0],[-1,1,0,0]]
findStep(matrix2)
puts "----------------------------------------------------"
matrix3 = [[0,0,1,-1],[0,1,-1,0],[0,-1,1,0],[-1,1,0,0]]
findStep(matrix3)
puts "----------------------------------------------------"
matrix4 = [[0,-1,-1,-1],[0,-1,1,1],[0,-1,1,0],[-1,1,0,0]]
findStep(matrix4)